#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "mpi.h"

//#define PRINTDEBUG

#define MAXLEN 100
#define MAXSLEN 15000

#define MIN(a,b)	((a) < (b) ? (a) : (b))
#define MAX(a,b)	((a) > (b) ? (a) : (b))

char	sname[MAXLEN], tname[MAXLEN];
char	sstring[MAXSLEN];
char	tstr[MAXSLEN];
char	tstring[MAXLEN][MAXSLEN];
int	lcs[MAXSLEN][MAXSLEN];
int	slen, tlen;

int 	final_lcs;
double  similarity;

int seil(int a , int b)
{
	if (a%b == 0)
		return a/b;
	else
		return a/b + 1;
}

void readfile (char *filename, char *string)
{
	FILE *sfp;
	int len;
	if ((sfp = fopen(filename, "r")) == NULL) 
	{
		fprintf(stderr, "lcs1:  can't open %s\n", filename);
		exit(1);
	}
//	printf("filename:%s\n",filename);
	len = fread(string, 1, MAXSLEN, sfp);
	fclose(sfp);
	string[--len] = '\0';
//	printf("string:%s\n",string);
}

void calculate(char *sstring, char *tstring)
{
	int	i, j;
	lcs[0][0] = 0;
	int slen = strlen(sstring);
	int tlen = strlen(tstring);
	for (j = 1; j <= tlen; j++) {
		lcs[0][j] = lcs[0][j-1];
	}

	for (i = 1; i <= slen; i++) {
		lcs[i][0] = lcs[i-1][0];

		for (j = 1; j <= tlen; j++) {
			lcs[i][j] = MAX(lcs[i-1][j], lcs[i][j-1]);

			if (sstring[i-1] == tstring[j-1]) {
				lcs[i][j] = MAX(lcs[i][j], lcs[i-1][j-1] + 1);
			} else {
				lcs[i][j] = MAX(lcs[i][j], lcs[i-1][j-1]);
			}
		}
	}
	
	final_lcs = lcs[slen][tlen];
	similarity = (double)lcs[slen][tlen] / MIN(slen, tlen);

#ifdef PRINTDEBUG
	printf("\nLCS matrix:\n");
	printf("      ");
	for (j = 1; j <= tlen; j++)
		printf(" %c ", tstring[j-1]);
	printf("\n");
	printf("   ");
	for (j = 0; j <= tlen; j++)
		printf("%3d", lcs[0][j]);
	printf("\n");
	for (i = 1; i <= slen; i++) {
		printf(" %c ", sstring[i-1]);
		for (j = 0; j <= tlen; j++)
			printf("%3d", lcs[i][j]);
		printf("\n");
	}
	printf("\n");
#endif
}

int main(int argc, char *argv[]) {
	double	t1, t2;
	int size,rank;
	FILE *tfp;
	int number=0;
	int from,tag;
	MPI_Status status;

	MPI_Init(&argc,&argv);
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);
	MPI_Comm_size(MPI_COMM_WORLD,&size);
	from = MPI_ANY_SOURCE;
	tag = MPI_ANY_TAG;

	if (rank == 0)
	{
		switch(argc) {
			case 3:
				strcpy(sname, *++argv);
				strcpy(tname, *++argv);

				break;
			default:
				fprintf(stderr, "usage: lcs1 sfile tfile\n");
				exit(1);
				break;
		}

		if ((tfp = fopen(tname, "r")) == NULL) {
			fprintf(stderr, "lcs1:  can't open %s\n", tname);
			exit(1);
		}
//		printf("tname:%s\n",tname);

		int tlen2;
		char tstring1[MAXSLEN];
		char list[MAXLEN][MAXLEN];
		fgets(tstr, MAXLEN, tfp);
		while(!feof(tfp))
		{
			tlen = strlen(tstr);
			strncpy(tstring1,tstr,tlen-2);
			tstring1[tlen-2]='\0';
			strcpy(list[number],tstring1);
			fgets(tstr, MAXLEN, tfp);
			number ++;
		}
		fclose(tfp);

		int a;
		for ( a = 0 ; a < size ; a ++)
		{
			MPI_Send(&number, 1, MPI_INT, a, 1, MPI_COMM_WORLD);
		}
		for (a=0 ; a<number ; a++)
		{
			MPI_Send(list[a],MAXLEN,MPI_CHAR,a%size, a, MPI_COMM_WORLD);
		}

	}
	
	MPI_Recv(&number,1, MPI_INT, from, tag, MPI_COMM_WORLD, &status);
	int st_count, st_source, st_tag;

	int a;
	for (a = 0 ; a < number ; a ++)
	{
		if (rank == a % size)
		{	
			char tstring3[MAXLEN];
			MPI_Recv(tstring3, MAXLEN, MPI_CHAR, from, tag, MPI_COMM_WORLD, &status);
			st_source= status.MPI_SOURCE;
			st_tag= status.MPI_TAG;
			MPI_Get_count(&status, MPI_CHAR, &st_count);

			tstring3[st_count] = '\0';
			readfile(tstring3,tstring[a]);
		}
	}

	int sslen = 0;

	if(rank == 0)
	{
		sslen = strlen(sname);
	}

	MPI_Bcast(&sslen, 1, MPI_INT, 0, MPI_COMM_WORLD);
	MPI_Bcast(sname, sslen, MPI_CHAR, 0, MPI_COMM_WORLD);
	readfile(sname,sstring);
	for (a = 0 ; a < number ; a ++)
	{
		if (rank == a % size)
		{	
			calculate(sstring,tstring[a]);
			double ad[3];
			ad[0] = (double)st_tag;
			ad[1] = (double)final_lcs;
			ad[2] = similarity;

			MPI_Send(ad, 3, MPI_DOUBLE, 0, 1 , MPI_COMM_WORLD);	
		}
	}
	if(rank ==0)
	{
	for(a = 0 ; a < number ; a ++)
	{
		double buf[3];
		MPI_Recv(buf,3,MPI_DOUBLE,from,tag,MPI_COMM_WORLD,&status);
		printf("%d,%d,%1.2f\n",(int)buf[0], (int)buf[1], buf[2]);
	}
	}
//	printf("%d: I am going to die.\n", rank);
	MPI_Finalize();
	return 0;
}

